package cn.cxq.learning.tree;

import java.util.ArrayList;

/**
 * 牛客题霸-全部题目
 * 实现二叉树先序，中序和后序遍历
 * 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M 热度指数：90548
 * 本题知识点： 栈 树 哈希
 *  算法知识视频讲解
 * 题目描述
 * 分别按照二叉树先序，中序和后序打印所有的节点。
 * 示例1
 * 输入
 * 复制
 * {1,2,3}
 * 返回值
 * 复制
 * [[1,2,3],[2,1,3],[2,3,1]]
 * 备注:
 * n \leq 10^6n≤10
 * 6
 *
 * 说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
 *  关联企业
 * 字节跳动商汤科技阿里巴巴菜鸟网络
 *  关联职位
 * 研发算法测试前端
 */
public class ThreeOrders {

    public int[][] threeOrders (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();

        preorderTransversal(list,root);

        int[][] result = new int[3][list.size()];
        int index = 0;
        for (int item : list) {
            result[0][index++] = item;
        }
        list.clear();
        inorderTransversal(list,root);

        index = 0;
        for (int item : list) {
            result[1][index++] = item;
        }
        list.clear();

        postorderTransversal(list,root);

        index = 0;
        for (int item : list) {
            result[2][index++] = item;
        }

        return result;
    }

    private void preorderTransversal(ArrayList<Integer> list, TreeNode node){
        if (node != null) {
            list.add(node.val);
            preorderTransversal(list,node.left);
            preorderTransversal(list,node.right);
        }
    }

    private void inorderTransversal(ArrayList<Integer> list, TreeNode node){

        if (node != null) {
            inorderTransversal(list,node.left);
            list.add(node.val);
            inorderTransversal(list,node.right);
        }
    }

    private void postorderTransversal(ArrayList<Integer> list, TreeNode node){
        if (node != null) {
            postorderTransversal(list,node.left);
            postorderTransversal(list,node.right);
            list.add(node.val);
        }
    }
}
